package com.leetcode.test.linklist.doublePoint;

import com.leetcode.test.linklist.ListNode;
import org.junit.Assert;
import org.junit.Test;

/**
 * 环形链表
 * <p>
 * 问题：https://leetcode-cn.com/explore/learn/card/linked-list/194/two-pointer-technique/744/ <br>
 * 官方解答：https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode/
 */
public class CycleLinkList {

    @Test
    public void testA() {
//        输入：head = [3,2,0,-4], pos = 1
//        输出：true
//        解释：链表中有一个环，其尾部连接到第二个节点。
        ListNode node3  = new ListNode(3);
        ListNode node2  = new ListNode(2);
        ListNode node0  = new ListNode(0);
        ListNode node_4 = new ListNode(-4);

        node3.next = node2;
        node2.next = node0;
        node0.next = node_4;
        node_4.next = node2;

        Assert.assertTrue(hasCycle(node3));
    }

    @Test
    public void testB() {
//        输入：head = [1], pos = -1
//        输出：false
//        解释：链表中没有环。
        ListNode node1 = new ListNode(1);

        Assert.assertFalse(hasCycle(node1));
    }

    // 双指针解法
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    // 哈希表解法
//    public boolean hasCycle(ListNode head) {
//        Set<ListNode> nodesSeen = new HashSet<>();
//        while (head != null) {
//            if (nodesSeen.contains(head)) {
//                return true;
//            } else {
//                nodesSeen.add(head);
//            }
//            head = head.next;
//        }
//        return false;
//    }



}
